public class Fixbag01{
    public static void main(String[] args) {
        //bag01的空间复杂度优化
        /*
        之前是有一个主循环 i=1..N，
        每次算出来 二维数组 f[i][0..V]的所有值。
        那么，如果只用一个数组 f[0..V]，能不能保证 第 i 次循环结束后 f[v]中表示的就是我们定义的状态 f[i][v]呢？
        f[i][v]是由 f[i-1][v]和 f[i-1][v-c[i]]两个子问题递推而来，
        能否保证在推 f[i][v]时（也 即在第 i 次主循环中推 f[v]时）能够得到 f[i-1][v]和 f[i-1][v-c[i]]的值呢？
        事实上，这要求在每次主循环中我们以 v=V..0 的顺序推 f[v]，
        这样才能保证推 f[v]时 f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。
        */
        int[] items_volume = {0, 2, 5, 3, 3, 1 ,5 ,2 ,4 ,7 ,1 };
        int[] items_cost =   {0, 3, 3, 6, 1, 1, 2, 2, 3, 4, 2 };
        int N = items_volume.length;
        int V = 8;

        int[] dp = new int[V+1];

        for(int i=1;i<N;i++){
            for(int v=V;v>=0;v--){
                if(v-items_volume[i] > 0)
                    dp[v] = Math.max(dp[v],dp[v-items_volume[i]]+items_cost[i]);
            }
        }

        System.out.println(dp[V]);
    }
}

/*
小技巧：
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。
有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。 
一种区别这两种问法的实现方法是在初始化的时候有所不同。 
如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f[0]为 0 其它 f[1..V]均设为-∞，
这样就可以保证最终得到的 f[N]是一种恰好装满背包的最优解。 
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 f[0..V]全部设为 0。 
为什么呢？
可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放入背包时的合法状态。
如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的 nothing “恰好装满”，其它容量的背包均没有合法的解，
属于未定义的状态，它们的值就都应该是-∞了。
如果背包并非必须被装满，
那么任何容量的背包都有一个合法解“什么都不装”，
这个解的价值为 0，所以初始时状 态的值也就全部为 0 了
*/